Corelab Seminar
2010-2011
Themis Gouleakis ( NTUA)
A constructive proof of the general Lovasz Local Lemma
Abstract.
The Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. In his breakthrough paper [Bec91], Beck demonstrated that a constructive variant can be given under certain more restrictive conditions. Simplifications of his procedure and relaxations of its restrictions were subsequently exhibited in several publications [Alo91, MR98, CS00, Mos06, Sri08, Mos08].
In this talk, we will present the recent work: [R. Moser and G. Tardos, 2009], and give a constructive proof using almost the same restrictions as in the existential proof.